package 学习计划.算法基础;

import java.util.ArrayList;
import java.util.List;

/**
 * 滑动窗口
 */
public class Study05 {

    public static void main(String[] args) {

        System.out.println(numSubarrayProductLessThanK(new int[]{1, 2, 3}, 0));

        System.out.println(findAnagrams("abab", "ab"));

    }

    //713. 乘积小于 K 的子数组
    //给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int cnt = 0;
        int sum = 1;
        int left = 0, right = 0;
        while (left < nums.length) {
            while (right < nums.length && sum < k) {
                sum *= nums[right];
                right++;
            }
            cnt += right - left;
            if (sum >= k) {
                cnt--;
            }
            sum /= nums[left];
            left++;
        }
        return cnt;
    }

    //438. 找到字符串中所有字母异位词
    //给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
    //异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int[] pRecord = new int[26];
        for (char c : p.toCharArray()) {
            pRecord[c - 'a']++;
        }
        int[] sRecord = new int[26];
        int left = 0, right = 0;
        while (left <= s.length() - p.length()) {
            while (right - left + 1 <= p.length()) {
                sRecord[s.charAt(right) - 'a']++;
                right++;
            }

            boolean flag = true;
            for (int i = 0; i < sRecord.length; i++) {
                if (sRecord[i] != pRecord[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                list.add(left);
            }
            sRecord[s.charAt(left) - 'a']--;
            left++;
        }
        return list;
    }

}
